//
//  SortedListToBST.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/8/18.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  109. 有序链表转换二叉搜索树

import UIKit

/*
 109. 有序链表转换二叉搜索树
 
 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

 示例:

 给定的有序链表： [-10, -3, 0, 5, 9],

 一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

       0
      / \
    -3   9
    /   /
  -10  5
 */

class SortedListToBST: NSObject {
    //链表是升序的  二叉搜索树的中序遍历也是升序的
    //可以先把链表转成数组 然后直接构建平衡二叉树。
    //也可以通过对链表的操作同样找到中间位置的节点，然后左右递归构建平衡二叉树
    func sortedListToBST(_ head: ListNode?) -> TreeNode? {
        
        guard head != nil else{
            return nil
        }
        guard head!.next != nil else {
            return TreeNode.init(head!.val)
        }
        
        //双指针遍历链表 p2的速度是p1的2倍，这样当 p2 = nil 或者 p2.next = nil 的时候，p1就指向链表的中间节点
        
        //找到链表中位数后 要切断链表 然后前后递归 因此再多加这一个指针
        var cutPoint = head
        
        var p1 = head
        var p2 = head
        
        while p2 != nil && p2?.next != nil {
            cutPoint = p1
            p1 = p1?.next
            p2 = p2?.next?.next
        }
        
        //此时p1指向了链表的中间节点
        //剪断链表
        cutPoint?.next = nil
        
        let root:TreeNode = TreeNode.init(p1!.val)
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(p1?.next)
        
        return root
    }
}
